//Build Pattern DataBase

/* This program performs a breadth-first search of a Pancake puzzle,
   starting from the goal state, but only keeping track of N pattern tiles and
   the blank position. It records the number of moves made by the N pattern
   tiles, for each state of this abbreviated space.  This version maintains a
   reference count vector to keep track of the number of pattern-tile moves to
   reach each state. This version hashes a state permutation exactly into an
   integer base factorial. This version uses disk files for the queues. This
   version stores the visited array one bit per element. This version doesn't
   build the heurisitic table in memory, but prints out pairs of indices and
   heuristic values.  The BUILD program then scans this output file to build the
   table. 
*/

#include <stdio.h> /* standard I/O library */
#include <stdlib.h>                                  
#include <math.h>

#include <string.h>
#include "defs.h"
typedef unsigned long int I64;

I64 goalindex;                       /* index of pattern tiles in their goal positions */

I64 maxHashvalue;
long totalHValues;

void readstate(int tilepos[PATTERNSIZE]); //done
void writestate (int tilepos[PATTERNSIZE]);//done
void write (int index,char hval);            //done
unsigned char  generated (I64 index,unsigned char hVal); //done
I64 hash (int perm[PATTERNSIZE]);   //done
bool MakeMove(int *m_pop,int *m_son,int iMove);  //done
void PrintArray(int *arr);                       //done
void PrintArray(int *arr,int inSize);//done
void PrintTiles(int *m_tiles);//done
void saveHuristicTable();
void ConverteTilesToTilesPos(int pop[SIZE], int tilepos[PATTERNSIZE]);
FILE *infile;                                              /* pointer to queue file to read from */
FILE *outfile;                                              /* pointer to queue file to write to */
FILE *pairfile;                     /* pointer to file for pairs of indices and heuristic values */
void GetStateFromTilePos(int tilepos[PATTERNSIZE],int pop[SIZE]);
int arrPatternLocation[SIZE]; // if the tile is not part of the pattern have the value -1 else its location
int arrPatternTiles[PATTERNSIZE]; //who does location i reffer to?

unsigned char visited[TABLESIZE];   /* 1 if a state has already been generated and written, zero otherwise */

I64 pairs;                            /* number of pairs of indices and heuristic values written */




void saveHuristicTable()
{
	unsigned char val;
	I64 mTotal=0;
	for(I64 i=0;i<TABLESIZE;++i)
	{
		val = visited[i];
		putc (val, pairfile);
	}
}


/* BFS takes a depth and a number of states in the input file, and performs one
    level of a breadth-first search of the space defined by the pattern
    tiles. Internally, it maintains a queue of nodes all of which have the
    pattern tiles in the same position, and draws from this queue.  When it
    becomes empty, it reads another state from the input file.  States that
    result from moves of the blank are placed in the internal queue, and states
    that result from moves of any of the pattern tiles are written to the output
    file.  It fills in the heuristic table H with the minimum number of moves of
    the pattern tiles to get them to all possible positions. */

int bfs (int level, int oldstates)
{
	int newstates;                                      /* the number of states in the output queue */
	int tilepos[PATTERNSIZE];                                /* positions of pattern tiles and blank at end */	
	int pop[SIZE];
	int son[SIZE];
	int move;                                                              /* index into move table */
	I64 stateindex,popIndex;                                      /* unique index of complete state */

	newstates = 0;                                            /* initially no states in output file */

	while (oldstates > 0)                         /* while there are still states in the input file */
	{
		readstate(tilepos);/* read state from input file */
		GetStateFromTilePos(tilepos,pop);
		oldstates--;                                      /* decrement number of states in input file */
		popIndex = hash(tilepos);

		for (move = 0; move < SIZE; move++)              /* for each applicable operator */
		{
			MakeMove(pop,son,move);
			ConverteTilesToTilesPos(son, tilepos);
			stateindex = hash(tilepos); /* unique index of complete state */
			if (!generated(stateindex,level+1))        /* state hasn't been visited before, mark as visited */
			{
				 totalHValues = totalHValues + level+1;
				 pairs++;
				 writestate(tilepos);                             /* write entire state to output file */
				 newstates++;
			}                            /* increment number of states in output file */
		}
	}
	return(newstates);
}
 


I64  hash(int perm[PATTERNSIZE])
{

	int i,digit,j;
	I64 hashval = 0;
	for (i = 0; i < PATTERNSIZE; i++)                         /* for each remaining position in permutation */
    {
		digit = perm[i] ;                                  /* initially digit is value in permutation */
		for (j = 0; j < i; j++)                           /* for each previous element in permutation */
			if (perm[j] < perm[i]) digit--; /* previous position contains smaller value, decrement digit*/
		hashval = hashval * (SIZE - i) + digit;
	}              /* multiply digit by appropriate factor */
	maxHashvalue = MAX(hashval,maxHashvalue);
	return hashval;
}


/* GENERATED takes a full state index and returns 1 if the state has been
   generated before, and 0 otherwise. In either case, it sets the bit to one if
   it wasn't already.  */
unsigned char generated (I64 index,unsigned char hVal)
{
	I64 entry;
	unsigned char leftVal,rightVal,val;

	if (index == goalindex)
		return 1;

	if (SHRINKDATABASE)
	{
		entry =  index>>1;
		if (entry >= TABLESIZE)
		{
			printf("\nFailed in building table - TABLESIZE too small\n");
			printf("Found index %u ,while TABLESIZE = %u\n",index,TABLESIZE);
			exit(0);
		}
		val = visited[entry];
		leftVal = val>>4;
		rightVal = val&15;

		if ((entry<<1)==index)
		{//so value in 4 left bits
			if (leftVal == 0)
			{//so need to update
				if (hVal>15)
				{
					printf("Faile writing data to table - Value %d bigger then 15\n",hVal);
					printf("Dont Shirink table\n");
					exit(0);
				}
				visited[entry] = ((hVal<<4)|rightVal);
				return 0;
			}
			else
				return 1;
		}
		else
		{//so value in 4 right bits)
			if (rightVal == 0)
			{//so need to update
				visited[entry] = ((leftVal<<4)|hVal);
				if (hVal>15)
				{
					printf("Faile writing data to table - Value %d bigger then 15\n",hVal);
					printf("Dont Shrink table\n");
					exit(0);
				}
 				return 0;
			}
			else
				return 1;//already exist

		}
//		printf("Index - %u entry- %u\n",index,entry);

	}
	else
	{
		if (index >= TABLESIZE)
		{
			printf("\nFailed in building table - TABLESIZE too small\n");
			printf("Found index %u ,while TABLESIZE = %u\n",index,TABLESIZE);
			exit(0);
		}
		if (visited[index] == 0)
		{
			visited[index] =hVal;
			return 0;
		}
	}
	return 1;
}                                                    /* return old value of bit */


/* WRITE takes an index and a heuristic value, and writes them to the pairsfile in 5 bytes */
void write (int index,char hval)
{
 putc (index >> 24, pairfile);
 putc (index >> 16 & 255, pairfile);
 putc (index >> 8 & 255, pairfile);
 putc (index & 255, pairfile);
 putc (hval, pairfile);
 //index is the permotation hval is the depth
}

/* WRITESTATE takes a vector of tile positions , and writes it to
   the output file*/


void writestate (int tilepos1[PATTERNSIZE])
{int i;                                                       /* index into tile positions */
 for (i = 0; i < PATTERNSIZE; i++)                   /* for each pair of tile positions */
   putc (tilepos1[i], outfile);    /* pack two into byte and output to file */
//printf("\nwrite - ");PrintArray(tilepos1,PATTERNSIZE+1);printf("\n");
}                           /* odd number of positions */

/* READSTATE reads a state from the input file, 2 tiles per byte, and unpacks it
   into the tilepos array. It is the inverse of writestate */

void readstate (int tilepos1[PATTERNSIZE])
{int i;                                                             /* index into tile positions */
 int byte;  
 for (i = 0; i < PATTERNSIZE; i ++)                                 /* for each pair of tile positions */
   {byte = getc(infile); /*  read byte from file */
 tilepos1[i] = (int)byte ;}                                         /* high order nibble */
 //printf("\nread - ");PrintArray(tilepos1,PATTERNSIZE+1);printf("\n");

}

void chooseName(char* argv[],int argc,char name[])
{
	char ch[5];
	itoa(SIZE,ch,10);
	strcpy(name,"Size");
	strcat(name,ch);
	strcat(name,"Pattern")	;
	for(int i=1;i<PATTERNSIZE+1;++i)
	{
		strcat(name,"_");
		strcat(name,argv[i]);
	}
}
/* main program inputs the tile numbers in the pattern, computes the pattern
   database], and prints out the values in the pattern database that don't equal
   the sum of the manhattan distances of the pattern tiles.  */

void get_input_parameters(int argc, char *argv[], int State[SIZE])
{
	int number1,acc =0;

	for (int i = 0; i < SIZE; i++)
	{
		State[i]=-1;
		arrPatternLocation[i] = -1;
	}

	//0 - the first symbol get -1     Note Symbole 0 belong to pattern automaticly
	//The second symbol get 0 
	//The 3rd get 1...

	for (int i=0;i<PATTERNSIZE;i++)
	{
		number1 = atoi(argv[i+1]);
		State[number1] = number1;
		arrPatternLocation[number1] = i;
		arrPatternTiles[i] = number1;
		acc++;
	}
}	

void AllocateMemory()
{
	I64 state;
	maxHashvalue = 0;
	totalHValues = 0;

	if (SHRINKDATABASE)
	{
		for(state = 0; state < TABLESIZE; state++)            /* initialize visited states to empty */
			visited[state] = 0; 
	}
	else
	{
		for (state = 0; state < TABLESIZE; state++)            /* initialize visited states to empty */
			visited[state] = 0; 
	}
}

void main (int argc,char *argv[])
{
 	 int pop[SIZE];

	 int tilepos[PATTERNSIZE];                                  /* positions of each pattern tile in a state */
	 I64 hash(int []);                            /* hash function returns I64 */
	 int level;                             /* current depth, equal to depth of states in input file */
	 int newstates;                                               /* number of states in output file */
	 int oldstates;                                        /* the number of states in the input file */

	 /*Initialize TopSpin */
	 AllocateMemory();
	 get_input_parameters(argc,argv, pop);
	 printf("My Pattern: ");PrintArray(pop,SIZE);printf("\n");
	 /*End of Initialize TopSpin */
	 ConverteTilesToTilesPos(pop, tilepos);

	 goalindex = hash(tilepos); /* compute index of goal state */

	 generated(goalindex,0);                                     /* mark goal state as already visited */
	 char name[100]={'\0'};
	 chooseName(argv,argc,name);
	 pairfile = fopen (name, "wb");              /* output file for pairs of indices and h values */
	 pairs = 1;                                                           /* one pair in output file */
	 newstates = 1;                                               /* only one newstate to start with */
	 outfile = fopen("q.1", "wb");                           /* write new states to file 1 in binary */
	 writestate (tilepos);                     /* write each pattern tile plus blank, to output file */
	 fclose(outfile);                                          /* close file before opening for read */
	 level = 0;
	 printf("%d %d\n", level, newstates);                    /* print statistics for the iteration */
	 /* start with reading initial state at depth 0 */
	 while (newstates > 0)                /* while there are still states that haven't been expanded */
	   {if (level % 2 == 0)                                                  /* even level of search */
		 {infile = fopen("q.1", "rb");                      /* read old states from file 1 in binary */
		 outfile = fopen("q.2", "wb");}                      /* write new states to file 2 in binary */
	   else                                                 /* otherwise, do it the other way around */
		 {infile = fopen("q.2", "rb");                      /* read old states from file 2 in binary */
		 outfile = fopen("q.1", "wb");}                      /* write new states to file 1 in binary */
	   oldstates = newstates;                            /* previously new states are now old states */
	   newstates = bfs(level, oldstates);                  /* perform breadth-first search iteration */
	   level = level + 1;                                                  /* increment search level */
	   printf("%d %d\n", level, newstates);                    /* print statistics for the iteration */
	   fflush(stdout);                                               /* flush buffer to see progress */
	   fclose(infile);                                                           /* close both files */
	   fclose(outfile);}
	 saveHuristicTable();
	 fclose(pairfile);                                                           /* close pairs file */
	 printf ("\ntotal states: %u\n", pairs);           /* total number of heuristic values written */
	 printf ("total H values of states %d\n",totalHValues); //total H values
	 if (SHRINKDATABASE)
		 printf ("Maximum entry Value %u (The smallest value for TABLESIZE Should be %u)\n",maxHashvalue>>1,(maxHashvalue+1)>>1);
	 else
		 printf ("Maximum entry Value %u (The smallest value for TABLESIZE Should be %u)\n",maxHashvalue,(maxHashvalue+1)); 

}             /* total number of states generated */




//*******************************************************************************
//*******************************************************************************
//*******************************************************************************
//*******************************************************************************
//*******************************************************************************
//*******************************************************************************
//*******************************************************************************
//*******************************************************************************
//*******************************************************************************

// Function name	: MakeMove
// Description	    : 
// Return type		: bool 
// Argument         : int *m_pop
// Argument         : int *m_son - will contain the result
// Argument         : int iMove
bool MakeMove(int *m_pop,int *m_son,int iMove)
{
	if (iMove < 0 || iMove >=SIZE) return false;
	
	int i;
	for (i = 0; i<= iMove ;i++)
	{
		m_son[i] = m_pop[iMove-i];
	}

	for (i= iMove +1 ; i<SIZE;i++)
		m_son[i] = m_pop[i];

	return true;
}

// Function name	: PrintArray
// Description	    : Prints the array
// Return type		: void 
// Argument         : int *arr
void PrintArray(int *arr)
{
	printf("Array[] = ");
	for (int i=0;i<SIZE;i++)
		printf("%d ",arr[i]);
	printf("\n");
}




// Function name	: PrintTiles
// Description	    : 
// Return type		: void 
// Argument         : int *m_tiles
void PrintTiles(int *m_tiles)
{
	printf("Tiles[] ");
	for (int i=0;i<PATTERNSIZE;i++)
		printf("%d ",m_tiles[i]);
	printf("\n");
}


// Function name	: PrintArray
// Description	    : 
// Return type		: void 
// Argument         : int *arr
// Argument         : int Size
void PrintArray(int *arr,int inSize)
{
	for (int i=0;i<inSize;i++)
		printf("%d ",arr[i]);
}


void ConverteTilesToTilesPos(int pop[SIZE], int tilepos[PATTERNSIZE])
{
	for (int i=0;i<SIZE;i++)
	{
		int tile = pop[i];
		if (tile!=-1)
		{
			if (arrPatternLocation[tile]!=-1)
				tilepos[arrPatternLocation[tile]] = i;
		}
	}
}

void GetStateFromTilePos(int tilepos[PATTERNSIZE],int pop[SIZE])
{

	for (int i=0;i<SIZE;i++)
		pop[i] = -1;

	for (int i=0;i<PATTERNSIZE;i++)
	{
		int loc = tilepos[i];
		int tile = arrPatternTiles[i];
		pop[loc] = tile;
	}
}